class Solution(object):
    def countRoutes(self, locations, start, finish, fuel):
        n = len(locations)
        DP = [[0] * n for _ in range(fuel + 1)]
        DP[fuel][start] = 1
        for i in range(fuel, 0, -1):
            for j in range(n):
                if DP[i][j]:
                    for k in range(n):
                        if k != j:
                            cost = abs(locations[j] - locations[k])
                            if i >= cost:
                                DP[i - cost][k] += DP[i][j]
        ans = 0
        for i in range(fuel + 1):
            ans += DP[i][finish]
        return ans

data = Solution()
locations = [2, 3, 6, 8, 4]
start = 1
finish = 3
fuel = 5
print(data.countRoutes(locations, start, finish, fuel))
locations = [2,1,5]
start = 0
finish = 0
fuel = 3
print(data.countRoutes(locations, start, finish, fuel))